
//
// 120228 - AH - Created.
//

package org.soekrat.engine.util;

/**
 * <p>
 *   Utility methods for working with longest common subsequence (LCS) and
 *   implementation of a 
 *   {@link StringMetric} based upon.
 * </p>
 * @author Arne Halvorsen (AH)
 */
public final class LCS extends StringMetric 
{
  /**
   * <p>
   *   Constructor.
   * </p>
   */
  public LCS(){}

  /**
   * <p>
   *   Metric based as defined here: 
   *   http://folk.uio.no/danielry/StringMetric.pdf
   * </p>
   * @param s0 First 
   *           {@link String}.
   * @param s1 Second
   *           {@link String}.
   * @return Metric.
   */
  public float metric(String s0, String s1)
  { 
    if (s0==null)
    {
      throw new NullPointerException("s0");
    }
    if (s1==null)
    {
      throw new NullPointerException("s1");
    }
    
    return lcsMetric(s0.toLowerCase(), s1.toLowerCase()); 
  }
  
  /**
   * <p>
   *   Metric based as defined here: 
   *   http://folk.uio.no/danielry/StringMetric.pdf
   * </p>
   * @param s0 First 
   *           {@link String}.
   * @param s1 Second
   *           {@link String}.
   * @return Metric.
   */
  public static float lcsMetric(String s0, String s1)
  {
    if (s0==null)
    {
      throw new NullPointerException("s0");
    }
    if (s1==null)
    {
      throw new NullPointerException("s1");
    }
    
    float lcs=(float)lcsLength(s0, s1);
    
    int l0=s0.length();
    int l1=s1.length();
    
    float m=l0>l1 ? l0 : l1;
    
    return 1.0f-lcs/m;
  }

  /**
   * <p>
   *   Computes LCS length.
   * </p>
   * @param s0 First 
   *           {@link String}.
   * @param s1 Second
   *           {@link String}.
   * @return Length.
   */
  public static int lcsLength(String s0, String s1)
  { 
    if (s0==null)
    {
      throw new NullPointerException("s0");
    }
    if (s1==null)
    {
      throw new NullPointerException("s1");
    }
    
    return lcs(s0, s1).length();
  }
  
  /**
   * <p>
   *   Computes LCS.
   * </p>
   * @param s0 First 
   *           {@link String}.
   * @param s1 Second
   *           {@link String}.
   * @return LCS.
   */
  public static String lcs(String s0, String s1)
  {
    if (s0==null)
    {
      throw new NullPointerException("s0");
    }
    if (s1==null)
    {
      throw new NullPointerException("s1");
    }
    
    StringBuilder sb=new StringBuilder();
    
    int M = s0.length();
    int N = s1.length();

    // opt[i][j] = length of LCS of x[i..M] and y[j..N]
    int[][] opt = new int[M+1][N+1];

    // compute length of LCS and all subproblems via dynamic programming
    for (int i = M-1; i >= 0; i--) 
    {
      for (int j = N-1; j >= 0; j--) 
      {
        if (s0.charAt(i) == s1.charAt(j))
          opt[i][j] = opt[i+1][j+1] + 1;
         else 
           opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
       }
     }

     // recover LCS itself and print it to standard output
     int i = 0, j = 0;
     while(i < M && j < N)
     {
       if (s0.charAt(i) == s1.charAt(j))
       {
         sb.append(s0.charAt(i));
         
         i++;
         j++;
       }
       else if (opt[i+1][j] >= opt[i][j+1]) i++;
       else                                 j++;
     }
    
    return sb.toString();
  }
 
  public static void main(String[] args) 
  {
    String s0 = "arne laetitia";
    String s1 = "jan laetia chatton";
    
    System.out.println(lcs(s0, s1));
    System.out.println(lcsMetric(s0, s1));
    
    System.out.println(lcsMetric("arne halvorsen", "arne tarvorsen"));
  }

}

